{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 补码\n",
    "\n",
    "参考：[Two’s Complement Representation: Theory and Examples](https://www.allaboutcircuits.com/technical-articles/twos-complement-representation-theory-and-examples/)\n",
    "\n",
    "[补码](https://en.wikipedia.org/wiki/Two%27s_complement)（英语：2's complement）是数字运算中的一种基本技术，它允许我们将减法运算替换为加法，常用于二进制表示有符号数的方法。补码以有符号比特的二进制数定义。\n",
    "\n",
    "$n$ 位二进制数 $N$ 的补码 $\\hat{N}$ 满足：$N + \\hat{N} = 2^n$(类比同余数概念)。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 背景：使用无符号数字进行计算\n",
    "\n",
    "假设我们有一个加法器，它可以接收两个四位数字 $a=a_3a_2a_1a_0$，$b=b_3b_2b_1b_0$ 以及一个进位输入（input carry）$c_{in}$，并且计算它们的和 $a+b+c_{in}$。如何使用加法器执行减法 $S = a-b$？将一个常数，如 $M$，加到 $S$ 上，然后再从 $S$ 中减去相同的常数，不会改变结果。\n",
    "\n",
    "```{math}\n",
    ":label: 1\n",
    "S=a+M-b-M\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于足够大的 $M$，有\n",
    "\n",
    "```{math}\n",
    ":label: 2\n",
    "B=M-b>0\n",
    "```\n",
    "\n",
    "则 {math:numref}`1` 可改写为\n",
    "\n",
    "```{math}\n",
    ":label: 3\n",
    "S=a+B-M\n",
    "```\n",
    "\n",
    "{math:numref}`3` 需要一次加法和一次减法运算。此外，还需要计算另一个减法，即 {eq}`2`。看起来我们把事情变得更复杂了，因为 $S = a - b$ 只需要一次减法运算，而 {math:numref}`3` 需要一次加法和两次减法运算！然而，注意到 {math:numref}`3` 所需的两个减法有一个共同点：这两个减法都涉及到一个公共操作数 $M$。这使我们想到，也许我们可以找到合适的 $M$，使得我们可以简化 {math:numref}`2` 和 {math:numref}`3` 的减法。如果可能的话，这将允许我们使用 {math:numref}`3` 将减法替换为加法。所以问题仍然是：对于常数 $M$，什么是一个合适的值？正如我们将在下一节中看到的那样，$M=2^k$ 被证明是适用于 $k$ 位数字的合适值。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假设 $b$ 是一个四位数字，我们来测验减法 $M-b$。使用 $M=10000_{(2)}=16_{(10)}$ 化简减法。这种简化是可能的，因为我们可以将 $M$ 表示为 $(M-1)+1$ 并得到 \n",
    "\n",
    "$$B=10000_{(2)}-b=(01111_{(2)}-b)+00001_{(2)}$$\n",
    "\n",
    "很容易计算 $01111_{(2)}-b$，这是因为它就是 $b$ 的按位反码（bitwise complement）。如果，$b=0011_{(2)}$，则\n",
    "\n",
    "$$\n",
    "B=(01111_{(2)}-0011_{(2)})+00001_{(2)}=01100_{(2)}+00001_{(2)}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "正如你所看到的，括号内的减法是 $b$ 的按位反码。因此，要执行减法 $M-b$，我们只需要找到 $b$的按位反码，然后将 $00001_{(2)}$ 加到结果中。我们将在本文后面看到，从实现的角度来看，将 $00001_{(2)}\n",
    "$ 加到一个数的按位反码上是一项简单的任务。这样 {eq}`3` 只剩 `-M` 需要处理。其实只需要丢弃第 $5$ 位上的位。这实际上等同于执行模 $M$ 计算，这意味着我们将计算结果限制在小于或等于 $M-1$ 的范围内。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{tip}\n",
    "以上讨论可以总结如下：如果 $a$ 和 $b$ 是两个 $k$$ 位数字，则可以通过将 $M-b$ 加到 $a$，并丢弃第 $k+1$ 位来计算减法 $a - b$。其中，称为补码常量(complementation constant)的 $M$ 等于 $2^k$。\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在模 $M$ 算术中，$M-b$ 充当 $b$ 的相反数，并称为 $b$ 的二进制补码（$M=2^k$）。这种相反的性质是显而易见的，因为将 $b$ 加到 $M-b$ 上会得到 $M$，这在模 $M$ 算术中等于 $0$。基于这个想法，我们可以定义 $b$ 的相反数为 $M-b$。如上所述，我们可以通过首先计算一个数的按位反码，然后将 1 添加到结果来计算该数的二进制补码。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假设我们正在处理无符号的四位数字。使用二进制补码表示法，有 $a=1011_{(2)}=11_{(10)}$，$b=0110_{(2)}=6_{(10)}$，则\n",
    "\n",
    "$$\n",
    "a-b=0101_{(2)}=5_{(10)}\n",
    "$$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "py37",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
